package com.example.demo.leetcode.codetop.bytedance;

/**
 * @author xujimou
 * @version 2.0
 * @Description
 *给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
 *
 * k 是一个正整数，它的值小于或等于链表的长度。
 *
 * 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
 *
 * 进阶：
 *
 * 你可以设计一个只使用常数额外空间的算法来解决此问题吗？
 * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
 *  
 *
 * 示例 1：
 *
 *
 * 输入：head = [1,2,3,4,5], k = 2
 * 输出：[2,1,4,3,5]
 * 示例 2：
 *
 *
 * 输入：head = [1,2,3,4,5], k = 3
 * 输出：[3,2,1,4,5]
 *
 * 示例 3：
 *
 * 输入：head = [1,2,3,4,5], k = 1
 * 输出：[1,2,3,4,5]
 * 示例 4：
 *
 * 输入：head = [1], k = 1
 * 输出：[1]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2022/2/23 14:32
 */
public class K个一组翻转链表 {


  public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }

    /**
     * @Desciption:
     *   使用头插法: k = 2 头
     *   插法是把  需要翻转的数  比如 2 3 4  从 2 3 开始头部插入， 2。3插完=>(3 2 4)，插 2 4
     *
     *        1-> 2 -> 3 ->4 ->5
     *    p   q   next
     *         -------->
     *        1    2 -> 3 ->4 ->5
     *    p   q   next
     *
     *     --> 2 ->  1  -->3 ->4 ->5
     *    p  next    q
     *     ->  2  -> 1  -> 3 -> 4 -> 5
     *               p     q
     *
     *   使用头插法: k = 3
     *
     *        1-> 2 -> 3 -> 4 -> 5
     *      p q  next
     *
     *        2-> 1 ->3 -> 4 ->5
     *    p       q  next
     * @param head:
     * @param k:
     */
    public ListNode reverseKGroup(ListNode head, int k) {

        ListNode p = new ListNode(-1);
        p.next = head;
        ListNode q = p,start = p;

        int count =0;
        while(head !=null){
            head=head.next;
            count++;
        }
        //总循环次数
        for(int i =0;i<count/k;i++){
            //循环几个数
            //q每次在p后面
            q = q.next;
            for(int j=0;j<k-1;j++){
                ListNode next = q.next;
                q.next = next.next;
                next.next = p.next;
                p.next = next;
            }
            //循环完一次后 p 后移
            for(int m=0;m<k;m++){
                p = p.next;
            }
            //q初始位置跟着p
            q = p;
        }
        return start.next;
    }



    public static void main(String[] args) {


    }
}
